package com.example.demo.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * TODO:两个数组的交集
 *
 * @date:2021/10/14 10:41
 * @author:Vicky(陈烟星)
 */
public class ArrayTest {

    /**
     * TODO:
     *  给定两个数组，编写一个函数来计算它们的交集。
     *   输入: nums1 = [1,2,2,1], nums2 = [2,2]
     *  输出: [2,2]
     *  输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
     *  我们可以不考虑输出结果的顺序。
     *   如果给定的数组已经排好序呢？将如何优化你的算法呢？
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] array1 = new int[]{1, 2, 3, 4, 4, 13};
        int[] array2 = new int[]{1, 2, 3, 9, 10};

        Map<Integer, Integer> map = new HashMap<>();
        for (int ele : array1) {
            if (map.containsKey(ele)) {
                map.put(ele, map.get(ele) + 1);
            } else {
                map.put(ele, 1);
            }
        }

        for (int ele : array2) {
            if (map.containsKey(ele) && map.get(ele) > 0) {
                // 打印
                System.out.println(ele);
                // 计数器--
                map.put(ele, map.get(ele) - 1);
            }
        }


//    --------------- 优化版本-----------------------

        // 初始化指针
        int pointer1 = 0;
        int pointer2 = 0;

        while (pointer1 < array1.length && pointer2 < array2.length) {
            int temp1 = array1[pointer1];
            int temp2 = array2[pointer2];

            if (temp1 == temp2) {
                // 打印
                System.out.println(temp1);
                pointer1++;
                pointer2++;
            } else if (temp1 < temp2) {
                pointer1++;
            } else {
                pointer2++;
            }
        }

    }
}
